| class FGAP_LIST{T} < $STR |
|---|
| **** | An array replacement for linked lists. The class `GAP_LIST{T}' is an array based list structure like `LIST{T}' but it supports insertions and deletions from the middle of the list as well as the end. This structure consists of an extensible array with a "gap" region in the middle. When an insertion or deletion is required, the gap is first moved to the proper location by moving elements around. Element access is by index and skips over the gap wherever it may lie. As long as most insertions and deletions are fairly close in location to the preceding one, the movement of elements accross the gap will not be extensive. Algorithms which are based on doubly linked lists often have a single pointer which moves up and down the list inserting and deleting elements as it moves. Such algorithms will also operate efficiently with gap lists. Sometimes this structure is refered to as a "double stack" since it may be viewed as two stack which approach one another. It has found wide use in text editors (such as GNU Emacs) and turns out to be much more efficient in practice than more obvious structures such as a linked list of strings for each line. |
| $STR | AREF{_} | COMPARE{_} |
| append(e: T): SAME |
|---|
| clear |
|---|
| **** | Clear the list. |
| create(a: $ELT{T}): SAME |
|---|
| create: SAME |
|---|
| **** | A new `GAP_LIST' with default `size=5'. |
| create_sized(n: INT): SAME |
|---|
| **** | A new `GAP_LIST' with `size=n'. |
| delete(i: INT): SAME |
|---|
| **** | Delete the `i'th element. |
| equals(e: $ARR{T}): BOOL |
|---|
| get(i: INT): T |
|---|
| **** | Retrieve the `i'th element. |
| has_ind(i: INT): BOOL |
|---|
| insert(i: INT, e: T): SAME |
|---|
| **** | Insert element `e' at location `i' pushing later elements forward. Elements may be inserted anywhere in the list or at the very end of the list |
| is_empty: BOOL |
|---|
| **** | True if `self' is empty. |
| replace(i: INT, e: T) |
|---|
| **** | Replace the `i'th element by `e'. |
| set(i: INT,val: T) |
|---|
| **** | Set the ith element |
| size: INT |
|---|
| **** | The total number of elements. |
| str: STR |
|---|
| **** | Prints out a string version of the flist of the components that are under $STR |
| elt!: T |
|---|
| set!(e: T) |
|---|
| aclear .. Included as aclear |
|---|
| **** | Set each element of self to nil. Built-in. |
| acopy(src:SAME) .. Included as acopy |
|---|
| **** | Copy as many elements from `src' to self as will fit. Built-in. |
| acopy(beg:INT, src:SAME) .. Included as acopy |
|---|
| **** | Copy as many elements from `src' to self as will fit when starting at index `beg' of self. |
| acopy(beg,num:INT, src:SAME) .. Included as acopy |
|---|
| **** | Copy `num' elements from `src' to self starting at index `beg' of self. |
| acopy(beg,num,srcbeg:INT, src:SAME) .. Included as acopy |
|---|
| **** | Copy `num' elements from `src' to self starting at index `beg' of self and index `srcbeg' of `src'. Built-in. |
| aelt!(once beg:INT):T .. Included as aelt! |
|---|
| **** | Yield each element of self starting at `beg'. Built-in. |
| aelt!(once beg,once num:INT):T .. Included as aelt! |
|---|
| **** | Yield `num' successive elements of self starting at index `beg'. Built-in. |
| aelt!(once beg,once num,once step:INT):T .. Included as aelt! |
|---|
| **** | Yield `num' elements of self starting at `beg' and stepping by `step' which must not be zero. Built-in. |
| aelt!:T .. Included as aelt! |
|---|
| **** | Yield each element of self in order. Built-in. |
| aget(ind:INT):T .. Included as aget |
|---|
| **** | The element of self with index `ind'. Built-in. |
| aind!:INT .. Included as aind! |
|---|
| **** | Yield the indices of self in order. |
| array_ptr:C_PTR .. Included as array_ptr |
|---|
| aset!(val:T) .. Included as aset! |
|---|
| **** | Set successive elements of self to the values `val'. Built-in. |
| aset!(once beg:INT,val:T) .. Included as aset! |
|---|
| **** | Set successive elements of self starting at `beg' to the values `val'. |
| aset!(once beg,once num:INT,val:T) .. Included as aset! |
|---|
| **** | Set `num' successive elements of self starting at `beg' to the values `val'. |
| aset!(once beg,once num,once step:INT, val:T) .. Included as aset! |
|---|
| **** | Set `num' elements of self starting at `beg' stepping by `step' to the values `val'. `step' must not be zero. |
| aset(ind:INT, val:T) .. Included as aset |
|---|
| **** | Set the element of self with index `ind' to `val'. Built-in. |
| asize:INT .. Included as asize |
|---|
| **** | The number of elements in self. Classes which inherit this may replace this by a constant to get constant sized objects (and the compiler may optimize certain operations in this case). Built-in. |
| create(n:INT):SAME .. Included as create |
|---|
| **** | A new array with `n' elements. |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| attr gap_start,gap_size: INT; |
|---|
| **** | Start of gap and size of gap. |
| attr gap_start,gap_size: INT; |
|---|
| **** | Start of gap and size of gap. |
| attr gap_start,gap_size: INT; |
|---|
| **** | Start of gap and size of gap. |
| attr gap_start,gap_size: INT; |
|---|
| **** | Start of gap and size of gap. |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| is_legal_aelts_arg( beg, num, step:INT) :BOOL .. Included as is_legal_aelts_arg |
|---|
| **** | True if the arguments are legal values for `aelts'. |
| move_gap(l: INT) |
|---|
| **** | Move the gap to start at `l'. Must have `l<=size'. |